package chapter_4.maxsubarray;

/**
 * (MaxSubArrayRecursion). 
 *
 * @author 汪文波(Wang Wenbo) wenboit@163.com
 * @notes Create on 2021-12-06 07:31
 */
public class Recursion {

    public static void main(String[] args) {
        int[] arr = {13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7};
        int[] max = Recursion.max(arr);
        System.out.printf("total: %d, index from %d to %d.", max[0], max[1], max[2]);
    }

    public static int[] max(int[] arr) {
        return Recursion.getMaxSubArray(arr, 0, arr.length);
    }

    public static int[] getMaxSubArray(int[] arr, int low, int high) {
        int[] result = new int[3];
        // base case
        // 左闭右开区间，只有一个元素
        if (low == high - 1) {
            result[0] = arr[low];
            result[1] = low;
            result[2] = low;
            return result;
        }
        // 分解，对每次分解都存在三种情况
        int mid = low + (high - low) / 2;
        int[] leftMax = getMaxSubArray(arr, low, mid);
        int[] rightMax = getMaxSubArray(arr, mid, high);
        int[] crossMax = getMaxCrossArray(arr, low, mid, high);
        // 合并
        if (leftMax[0] >= rightMax[0] && leftMax[0] >= crossMax[0]) {
            return leftMax;
        } else if (rightMax[0] >= leftMax[0] && rightMax[0] >= crossMax[0]) {
            return rightMax;
        } else {
            return crossMax;
        }
    }


    // 找出形如 arr[i..mid),arr[mid, j) 的最大子数组，然后合并
    public static int[] getMaxCrossArray(int[] arr, int low, int mid, int high) {
        int[] result = new int[3];
        // 左半区间
        int maxLeft = Integer.MIN_VALUE;
        int sumLeft = 0;
        // 左闭右开区间
        for (int i = mid - 1; i >= low; i--) {
            sumLeft += arr[i];
            if (maxLeft < sumLeft) {
                maxLeft = sumLeft;
                result[1] = i;
            }
        }
        // 右半区间
        int maxRight = Integer.MIN_VALUE;
        int sumRight = 0;
        // 左闭右开区间
        for (int i = mid; i < high; i++) {
            sumRight += arr[i];
            if (maxRight < sumRight) {
                maxRight = sumRight;
                result[2] = i;
            }
        }

        result[0] = maxLeft + maxRight;
        return result;
    }

}
